package leetcodev1.数组;

import other.Lru;

import java.util.Arrays;

public class LeetCode16 {

    //最接近target min(Math.abs(n1+n2+n3-target)) 差值绝对值最小
    //1.暴力解 三重循环
    //2.hash排除 因为需要找最接近，不是等值
    //3.排序
    public int threeSumClosest1(int[] nums, int target) {
        //异常处理
        if (nums == null || nums.length < 3) {
            return -1;
        }

        int ret = nums[0] + nums[1] + nums[2], tmpSum;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                for (int k = j + 1; k < length; k++) {
                    tmpSum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(tmpSum - target) < Math.abs(ret - target)) {
                        ret = tmpSum;
                    }
                }
            }
        }

        return ret;
    }

    //排序双指针
    public int threeSumClosest(int[] nums, int target) {
        //异常处理
        if (nums == null || nums.length < 3) {
            return -1;
        }

        Arrays.sort(nums);
        int length = nums.length, sum, ret = nums[0] + nums[1] + nums[2];
        //需要剩余两个元素
        for (int i = 0; i < length; i++) {
            //起始值不重复枚举
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            //left允许重复值
            int left = i + 1, right = length - 1;
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];

                if (Math.abs(sum - target) < Math.abs(ret - target)) {
                    ret = sum;
                }

                if (sum > target) {
                    right--;
                    //跳过重复元素
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < target) {
                    left++;
                    //跳过重复元素
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                } else {
                    return target;
                }
            }
        }
        return ret;
    }
}
